Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11137 - Ingenuous Cubrency / 11137.cpp
blob2958265f8e7e18fb2b2c4681de984ecf99ab51e3
1 /*
2 11137 - Ingenuous Cubrency [UVa Online Judge]
3 Andrés Mejía-Posada [http://blogaritmo.factorcomun.org]
5 Programación dinámica, coin change
7 Aceptado por el juez.
8 */
9 #include <iostream>
11 using namespace std;
13 const int COINS = 21, MONEY = 9999;
15 int coins[COINS];
18 dp[i][j] = Utilizando las primeras i monedas, de cuantas maneras puedo fomar exactamente j cubos?
20 unsigned long long dp[COINS][MONEY+1];
22 int main(){
23 for (int i=1; i<=COINS; ++i){
24 coins[i-1] = i*i*i;
27 for (int i=0; i<COINS; ++i){
28 dp[i][0] = 1ULL; //Cero cubos los puedo formar de una única manera: coger ninguna moneda.
29 for (int j=1; j<=MONEY; ++j){
30 dp[i][j] = 0ULL;
31 if (i > 0) dp[i][j] += dp[i-1][j];
32 if (j - coins[i] >= 0) dp[i][j] += dp[i][j - coins[i]];
36 int n;
37 while (cin >> n) cout << dp[COINS-1][n] << endl;
40 return 0;